#include "Queue.h"

void QueueInit(Queue *q)
{
    assert(q);
    q->head = q->tail = NULL;
}

void QueueDestory(Queue *q)
{
    assert(q);

    QNode *cur = q->head;
    while (cur)
    {
        QNode *next = cur->next;
        free(cur);
        cur = next;
    }
    q->head = q->tail = NULL;
}

void QueuePush(Queue *q, QDataType x)
{
    assert(q);

    //开辟新节点
    QNode *newnode = (QNode *)malloc(sizeof(QNode));
    //判空
    if (newnode == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    else
    {
        newnode->val = x;
        newnode->next = NULL;
    }

    //入队列
    if (q->head == NULL && q->tail == NULL)
    {
        //如果队头和队尾都为NULL，则它们同时指向头节点
        q->head = newnode;
        q->tail = newnode;
    }
    else
    {
        q->tail->next = newnode;
        //更新队尾
        q->tail = newnode;
    }
}

void QueuePop(Queue *q)
{
    assert(q);
    assert(q->head != NULL);

    //出队列(从队头出)
    if (q->head->next == NULL)
    {
        //当只有一个节点时，头被释放，tail还是指向原来的头节点，这将导致不确定性
        free(q->head);
        q->tail = q->head = NULL;
    }
    else
    {
        QNode *next = q->head->next;
        free(q->head);
        q->head = next;
    }
}

bool QueueEmpty(Queue *q)
{
    assert(q);
    return q->head == NULL;
}

size_t QueueSize(Queue *q)
{
    assert(q);
    assert(q->head);

    QNode *cur = q->head;
    size_t Size = 0;
    while (cur)
    {
        ++Size;
        cur = cur->next;
    }
    return Size;
}

QDataType QueueFront(Queue *q)
{
    assert(q);
    assert(q->head);

    return q->head->val;
}

QDataType QueueBack(Queue *q)
{
    assert(q);
    assert(q->tail);

    return q->tail->val;
}

//测试
int main()
{
    Queue q;
    //初始化队列
    QueueInit(&q);
    //入队列
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    QueuePush(&q, 5);
    QueuePush(&q, 6);
    //显示队列数据
    while (!QueueEmpty(&q))
    {
        printf("%d ", QueueFront(&q));
        //出队列
        QueuePop(&q);
    }
    printf("\n");

    Queue p;
    //初始化队列
    QueueInit(&p);
    //入队列
    QueuePush(&p, 1);
    QueuePush(&p, 2);
    QueuePush(&p, 3);
    QueuePush(&p, 4);
    QueuePush(&p, 5);
    QueuePush(&p, 6);

    //出队列
    QueuePop(&p);
    QueuePop(&p);
    //显示队列数据
    while (!QueueEmpty(&p))
    {
        printf("%d ", QueueFront(&p));
        //出队列
        QueuePop(&p);
    }

    printf("\n");
    system("pause");
    return 0;
}